class Bucket {
  min;
  max;
}

const getMaxSortedDistance = (array) => {

  //1.得到数列的最大值和最小值
  let max = array[0];
  let min = array[0];
  for (let i = 1; i < array.length; i++) {
    if (array[i] > max) {
      max = array[i];
    }
    if (array[i] < min) {
      min = array[i];
    }
  }
  let d = max - min;
  //如果max和min相等，说明数组所有元素都相等，返回0
  if (d === 0) {
    return 0;
  }

  //2.初始化桶
  let bucketNum = array.length;
  const buckets = new Array(bucketNum);
  for (let i = 0; i < bucketNum; i++) {
    buckets[i] = new Bucket();
  }

  //3.遍历原始数组，确定每个桶的最大最小值
  for (let i = 0; i < array.length; i++) {
    //确定数组元素所归属的桶下标
    let index = Math.floor((array[i] - min) * (bucketNum - 1) / d);
    if (buckets[index].min == null || buckets[index].min > array[i]) {
      buckets[index].min = array[i];
    }
    if (buckets[index].max == null || buckets[index].max < array[i]) {
      buckets[index].max = array[i];
    }
  }

  //4.遍历桶，找到最大差值
  let leftMax = buckets[0].max;
  let maxDistance = 0;
  for (let i = 1; i < buckets.length; i++) {
    if (buckets[i].min == null) {
      continue;
    }
    if (buckets[i].min - leftMax > maxDistance) {
      maxDistance = buckets[i].min - leftMax;
    }
    leftMax = buckets[i].max;
  }

  return maxDistance;
}
const run = () => {
  const array = [2, 6, 3, 4, 5, 10, 9];
  console.log(getMaxSortedDistance(array))
}
run()